题目描述

关系

内容

问题分析

最初思路

思路分析

执行流程设计

伪代码如下 (超时）：

input: 

sort increase

while (k--) {
	for (int i = 0; i < n; i++) {
		if (天梯赛成绩不达标 || 已经入选) continue;
		cnt++;
		int j = i + 1;
		while (j < n && 天梯j与i相同) {
			j++;
			if (未入选 && (PAT成绩达标 || 还有)) cnt++;
		}
		i = j - 1;
	}
}

input: 

sort increase

int score[N] (k - 1); //初始化为k, 表示还可以选score个同分数的人。

for (int i = 0; i < n; i++) {
	if (天梯赛成绩不达标) continue;
	cnt++;
	标记;
	int j = i + 1;
	while (j < n && 天梯j与i相同) {
		j++;
		if (PAT成绩达标)) {
			cnt++;
		} else if (score[j]) {
			score[j]--;
			cnt++;
		}
	}
	i = j - 1;
}

总结

代码实现

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second

typedef pair<int, int> pii;

const int N = 1e5 + 10;
int n, k, s, cnt;
pii a[N];

int main()
{
    scanf("%d%d%d", &n, &k, &s);
    for (int i = 0; i < n; i++) scanf("%d%d", &a[i].x, &a[i].y);
    
    sort(a, a + n);


    vector<int> score(300, k - 1);
    for (int i = 0; i < n; i++) {
        if (a[i].x < 175) continue;
        cnt++;
        int j = i + 1;
        while (j < n && a[j].x == a[i].x) {
            if (a[j].y >= s) {
                cnt++;
            } else if (score[a[i].x]) {
                score[a[i].x]--;
                cnt++;
            }
            j++;
        }
        i = j - 1;
    }
    printf("%d", cnt);
    return 0;
}